package time_complexity;

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

import java.util.Arrays;

public class Demo {
    public static void main(String[] args) {
        func1(10);
        int[] arr ={1,5,3,2,6,9,8,7,0,4};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println(fib(30));
        System.out.println(binarySearch(arr, 5));
    }
    //斐波那契数列的递归算法————时间复杂度O(2^n)
    public static int fib(int n){
        return n<2 ? n : fib(n - 1) + fib(n - 2);
    }
    //冒泡排序————时间复杂度为：O(n^2)
    public static void bubbleSort(int[] array){
        int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if(array[j] > array[j+1]){
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1]=tmp;
                }
            }
        }
    }
    //二分法查找————时间复杂度为O(log(n))
    public static int binarySearch(int[] array,int target){
        int left = 0;
        int right = array.length - 1;
        while(right > left){
            int mid = left + (right - left)/2;
            if(target == array[mid]){
                return mid;
            } else if (target < array[mid]) {
                right = mid;
            }else{
                    left = mid + 1;
            }
        }
        return -1;
    }
    //计算时间复杂度例题
    public static void func1(int N){
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                count++;
            }
        }
        for (int k = 0; k < 2 * N; k++) {
            count++;
        }
        int M = 10;
        while((M--)>0){
            count++;
        }
        System.out.println(count);
    }
}
